// queue standard header
#pragma once
#ifndef _QUEUE_
#define _QUEUE_
#ifndef RC_INVOKED
#include <algorithm>
#include <deque>
#include <vector>

#pragma pack(push, _CRT_PACKING)
#pragma warning(push, _STL_WARNING_LEVEL)
#pragma warning(disable : _STL_DISABLED_WARNINGS)
_STL_DISABLE_CLANG_WARNINGS
#pragma push_macro("new")
#undef new
_STD_BEGIN
// CLASS TEMPLATE queue
template <class _Ty,
    class _Container = deque<_Ty>>
class queue { // FIFO queue implemented with a container
public:
    using container_type  = _Container;
    using value_type      = typename _Container::value_type;
    using size_type       = typename _Container::size_type;
    using reference       = typename _Container::reference;
    using const_reference = typename _Container::const_reference;

    static_assert(is_same_v<_Ty, value_type>, "container adaptors require consistent types");

    queue() _NOEXCEPT_COND(is_nothrow_default_constructible_v<_Container>) // strengthened
        : c() { // construct with empty container
    }

    explicit queue(const _Container& _Cont) : c(_Cont) { // construct by copying specified container
    }

    template <class _Alloc, class = enable_if_t<uses_allocator_v<_Container, _Alloc>>>
    explicit queue(const _Alloc& _Al)
        _NOEXCEPT_COND(is_nothrow_constructible_v<_Container, const _Alloc&>) // strengthened
        : c(_Al) { // construct with empty container, allocator
    }

    template <class _Alloc, class = enable_if_t<uses_allocator_v<_Container, _Alloc>>>
    queue(const _Container& _Cont, const _Alloc& _Al)
        : c(_Cont, _Al) { // construct by copying specified container, allocator
    }

    template <class _Alloc, class = enable_if_t<uses_allocator_v<_Container, _Alloc>>>
    queue(const queue& _Right, const _Alloc& _Al)
        : c(_Right.c, _Al) { // construct by copying _Right container, allocator
    }

    explicit queue(_Container&& _Cont) _NOEXCEPT_COND(is_nothrow_move_constructible_v<_Container>) // strengthened
        : c(_STD move(_Cont)) { // construct by moving specified container
    }

    template <class _Alloc, class = enable_if_t<uses_allocator_v<_Container, _Alloc>>>
    queue(_Container&& _Cont, const _Alloc& _Al)
        _NOEXCEPT_COND(is_nothrow_constructible_v<_Container, _Container, const _Alloc&>) // strengthened
        : c(_STD move(_Cont), _Al) { // construct by moving specified container, allocator
    }

    template <class _Alloc, class = enable_if_t<uses_allocator_v<_Container, _Alloc>>>
    queue(queue&& _Right, const _Alloc& _Al)
        _NOEXCEPT_COND(is_nothrow_constructible_v<_Container, _Container, const _Alloc&>) // strengthened
        : c(_STD move(_Right.c), _Al) { // construct by moving _Right container, allocator
    }

    void push(value_type&& _Val) { // insert element at beginning
        c.push_back(_STD move(_Val));
    }

    template <class... _Valty>
    decltype(auto) emplace(_Valty&&... _Val) { // insert element at beginning
#if _HAS_CXX17
        return c.emplace_back(_STD forward<_Valty>(_Val)...);
#else // _HAS_CXX17
        c.emplace_back(_STD forward<_Valty>(_Val)...);
#endif // _HAS_CXX17
    }

    _NODISCARD bool empty() const { // test if queue is empty
        return c.empty();
    }

    _NODISCARD size_type size() const { // return length of queue
        return c.size();
    }

    _NODISCARD reference front() { // return first element of mutable queue
        return c.front();
    }

    _NODISCARD const_reference front() const { // return first element of nonmutable queue
        return c.front();
    }

    _NODISCARD reference back() { // return last element of mutable queue
        return c.back();
    }

    _NODISCARD const_reference back() const { // return last element of nonmutable queue
        return c.back();
    }

    void push(const value_type& _Val) { // insert element at beginning
        c.push_back(_Val);
    }

    void pop() { // erase element at end
        c.pop_front();
    }

    const _Container& _Get_container() const { // get reference to container
        return c;
    }

    void swap(queue& _Right) _NOEXCEPT_COND(_Is_nothrow_swappable<_Container>::value) { // exchange contents with _Right
        _Swap_adl(c, _Right.c);
    }

protected:
    _Container c; // the underlying container
};

#if _HAS_CXX17
template <class _Container, enable_if_t<!_Is_allocator<_Container>::value, int> = 0>
queue(_Container)->queue<typename _Container::value_type, _Container>;

template <class _Container, class _Alloc,
    enable_if_t<
        conjunction_v<negation<_Is_allocator<_Container>>, _Is_allocator<_Alloc>, uses_allocator<_Container, _Alloc>>,
        int> = 0>
queue(_Container, _Alloc)->queue<typename _Container::value_type, _Container>;
#endif // _HAS_CXX17

template <class _Ty, class _Container, class = enable_if_t<_Is_swappable<_Container>::value>>
inline void swap(queue<_Ty, _Container>& _Left, queue<_Ty, _Container>& _Right)
    _NOEXCEPT_COND(noexcept(_Left.swap(_Right))) { // swap _Left and _Right queues
    _Left.swap(_Right);
}

template <class _Ty, class _Container>
_NODISCARD inline bool operator==(
    const queue<_Ty, _Container>& _Left, const queue<_Ty, _Container>& _Right) { // test for queue equality
    return _Left._Get_container() == _Right._Get_container();
}

template <class _Ty, class _Container>
_NODISCARD inline bool operator!=(
    const queue<_Ty, _Container>& _Left, const queue<_Ty, _Container>& _Right) { // test for queue inequality
    return !(_Left == _Right);
}

template <class _Ty, class _Container>
_NODISCARD inline bool operator<(
    const queue<_Ty, _Container>& _Left, const queue<_Ty, _Container>& _Right) { // test if _Left < _Right for queues
    return _Left._Get_container() < _Right._Get_container();
}

template <class _Ty, class _Container>
_NODISCARD inline bool operator>(
    const queue<_Ty, _Container>& _Left, const queue<_Ty, _Container>& _Right) { // test if _Left > _Right for queues
    return _Right < _Left;
}

template <class _Ty, class _Container>
_NODISCARD inline bool operator<=(
    const queue<_Ty, _Container>& _Left, const queue<_Ty, _Container>& _Right) { // test if _Left <= _Right for queues
    return !(_Right < _Left);
}

template <class _Ty, class _Container>
_NODISCARD inline bool operator>=(
    const queue<_Ty, _Container>& _Left, const queue<_Ty, _Container>& _Right) { // test if _Left >= _Right for queues
    return !(_Left < _Right);
}

// CLASS TEMPLATE priority_queue
template <class _Ty, class _Container = vector<_Ty>,
    class _Pr = less<typename _Container::value_type>>
class priority_queue { // priority queue implemented with a _Container
public:
    using container_type  = _Container;
    using value_compare   = _Pr;
    using value_type      = typename _Container::value_type;
    using size_type       = typename _Container::size_type;
    using reference       = typename _Container::reference;
    using const_reference = typename _Container::const_reference;

    static_assert(is_same_v<_Ty, value_type>, "container adaptors require consistent types");

    priority_queue() _NOEXCEPT_COND(is_nothrow_default_constructible_v<_Container>&&
            is_nothrow_default_constructible_v<value_compare>) // strengthened
        : c(), comp() { // construct with empty container, default comparator
    }

    explicit priority_queue(const _Pr& _Pred) _NOEXCEPT_COND(
        is_nothrow_default_constructible_v<_Container>&& is_nothrow_copy_constructible_v<value_compare>) // strengthened
        : c(), comp(_Pred) { // construct with empty container, specified comparator
    }

    priority_queue(const _Pr& _Pred, const _Container& _Cont)
        : c(_Cont), comp(_Pred) { // construct by copying specified container, comparator
        _STD make_heap(c.begin(), c.end(), comp);
    }

    template <class _InIt>
    priority_queue(_InIt _First, _InIt _Last)
        : c(_First, _Last), comp() { // construct by copying [_First, _Last), default comparator
        _STD make_heap(c.begin(), c.end(), comp);
    }

    template <class _InIt>
    priority_queue(_InIt _First, _InIt _Last, const _Pr& _Pred)
        : c(_First, _Last), comp(_Pred) { // construct by copying [_First, _Last), specified comparator
        _STD make_heap(c.begin(), c.end(), comp);
    }

    template <class _InIt>
    priority_queue(_InIt _First, _InIt _Last, const _Pr& _Pred, const _Container& _Cont)
        : c(_Cont), comp(_Pred) { // construct by copying [_First, _Last), container, and comparator
        c.insert(c.end(), _First, _Last);
        _STD make_heap(c.begin(), c.end(), comp);
    }

    template <class _Alloc, class = enable_if_t<uses_allocator_v<_Container, _Alloc>>>
    explicit priority_queue(const _Alloc& _Al) _NOEXCEPT_COND(is_nothrow_constructible_v<_Container, const _Alloc&>&&
            is_nothrow_default_constructible_v<value_compare>) // strengthened
        : c(_Al), comp() { // construct with empty container, allocator
    }

    template <class _Alloc, class = enable_if_t<uses_allocator_v<_Container, _Alloc>>>
    priority_queue(const _Pr& _Pred, const _Alloc& _Al)
        _NOEXCEPT_COND(is_nothrow_constructible_v<_Container, const _Alloc&>&&
                is_nothrow_copy_constructible_v<value_compare>) // strengthened
        : c(_Al), comp(_Pred) { // construct with empty container, comparator, allocator
    }

    template <class _Alloc, class = enable_if_t<uses_allocator_v<_Container, _Alloc>>>
    priority_queue(const _Pr& _Pred, const _Container& _Cont, const _Alloc& _Al)
        : c(_Cont, _Al), comp(_Pred) { // construct by copying specified container, comparator, allocator
        _STD make_heap(c.begin(), c.end(), comp);
    }

    template <class _Alloc, class = enable_if_t<uses_allocator_v<_Container, _Alloc>>>
    priority_queue(const priority_queue& _Right, const _Alloc& _Al)
        : c(_Right.c, _Al), comp(_Right.comp) { // construct by copying _Right, allocator
    }

    priority_queue(const _Pr& _Pred, _Container&& _Cont)
        : c(_STD move(_Cont)), comp(_Pred) { // construct by moving specified container, comparator
        _STD make_heap(c.begin(), c.end(), comp);
    }

    template <class _InIt>
    priority_queue(_InIt _First, _InIt _Last, const _Pr& _Pred, _Container&& _Cont)
        : c(_STD move(_Cont)), comp(_Pred) { // construct by copying [_First, _Last), moving container
        c.insert(c.end(), _First, _Last);
        _STD make_heap(c.begin(), c.end(), comp);
    }

    template <class _Alloc, class = enable_if_t<uses_allocator_v<_Container, _Alloc>>>
    priority_queue(const _Pr& _Pred, _Container&& _Cont, const _Alloc& _Al)
        : c(_STD move(_Cont), _Al), comp(_Pred) { // construct by moving specified container, comparator, allocator
        _STD make_heap(c.begin(), c.end(), comp);
    }

    template <class _Alloc, class = enable_if_t<uses_allocator_v<_Container, _Alloc>>>
    priority_queue(priority_queue&& _Right, const _Alloc& _Al)
        _NOEXCEPT_COND(is_nothrow_constructible_v<_Container, _Container, const _Alloc&>&&
                is_nothrow_move_constructible_v<value_compare>) // strengthened
        : c(_STD move(_Right.c), _Al), comp(_STD move(_Right.comp)) { // construct by moving _Right, allocator
    }

    void push(value_type&& _Val) { // insert element at beginning
        c.push_back(_STD move(_Val));
        _STD push_heap(c.begin(), c.end(), comp);
    }

    template <class... _Valty>
    void emplace(_Valty&&... _Val) { // insert element at beginning
        c.emplace_back(_STD forward<_Valty>(_Val)...);
        _STD push_heap(c.begin(), c.end(), comp);
    }

    _NODISCARD bool empty() const { // test if queue is empty
        return c.empty();
    }

    _NODISCARD size_type size() const { // return length of queue
        return c.size();
    }

    _NODISCARD const_reference top() const { // return highest-priority element
        return c.front();
    }

    void push(const value_type& _Val) { // insert value in priority order
        c.push_back(_Val);
        _STD push_heap(c.begin(), c.end(), comp);
    }

    void pop() { // erase highest-priority element
        _STD pop_heap(c.begin(), c.end(), comp);
        c.pop_back();
    }

    void swap(priority_queue& _Right) _NOEXCEPT_COND(
        _Is_nothrow_swappable<_Container>::value&& _Is_nothrow_swappable<_Pr>::value) { // exchange contents with _Right
        _Swap_adl(c, _Right.c);
        _Swap_adl(comp, _Right.comp);
    }

protected:
    _Container c; // the underlying container
    _Pr comp; // the comparator functor
};

#if _HAS_CXX17
template <class _Pr, class _Container,
    enable_if_t<conjunction_v<negation<_Is_allocator<_Pr>>, negation<_Is_allocator<_Container>>>, int> = 0>
priority_queue(_Pr, _Container)->priority_queue<typename _Container::value_type, _Container, _Pr>;

template <class _Iter, class _Pr = less<_Iter_value_t<_Iter>>, class _Container = vector<_Iter_value_t<_Iter>>,
    enable_if_t<conjunction_v<_Is_iterator<_Iter>, negation<_Is_allocator<_Pr>>, negation<_Is_allocator<_Container>>>,
        int> = 0>
priority_queue(_Iter, _Iter, _Pr = _Pr(), _Container = _Container())
    ->priority_queue<_Iter_value_t<_Iter>, _Container, _Pr>;

template <class _Pr, class _Container, class _Alloc,
    enable_if_t<conjunction_v<negation<_Is_allocator<_Pr>>, negation<_Is_allocator<_Container>>, _Is_allocator<_Alloc>,
                    uses_allocator<_Container, _Alloc>>,
        int> = 0>
priority_queue(_Pr, _Container, _Alloc)->priority_queue<typename _Container::value_type, _Container, _Pr>;
#endif // _HAS_CXX17

template <class _Ty, class _Container, class _Pr,
    class = enable_if_t<_Is_swappable<_Container>::value && _Is_swappable<_Pr>::value>>
inline void swap(priority_queue<_Ty, _Container, _Pr>& _Left, priority_queue<_Ty, _Container, _Pr>& _Right)
    _NOEXCEPT_COND(noexcept(_Left.swap(_Right))) { // swap _Left and _Right queues
    _Left.swap(_Right);
}
_STD_END

namespace std {
    template <class _Ty, class _Container, class _Alloc>
    struct uses_allocator<queue<_Ty, _Container>, _Alloc>
        : uses_allocator<_Container, _Alloc>::type { // true_type if container allocator enabled
    };

    template <class _Ty, class _Container, class _Pr, class _Alloc>
    struct uses_allocator<priority_queue<_Ty, _Container, _Pr>, _Alloc>
        : uses_allocator<_Container, _Alloc>::type { // true_type if container allocator enabled
    };
} // namespace std

#pragma pop_macro("new")
_STL_RESTORE_CLANG_WARNINGS
#pragma warning(pop)
#pragma pack(pop)
#endif // RC_INVOKED
#endif // _QUEUE_

/*
 * Copyright (c) by P.J. Plauger. All rights reserved.
 * Consult your license regarding permissions and restrictions.
V6.50:0009 */
